#include<stdio.h>
#include<stdlib.h>
//现有一链表的头指针ListNode*pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序，
// 返回重新排列后的链表的头指针。
typedef struct ListNode
{
	int val;
	struct ListNode* next; 
}ListNode;

ListNode* partition(ListNode* pHead,int x)
{
	ListNode* l_traval = NULL;
	ListNode* s_traval = NULL;
	ListNode* large =l_traval= (ListNode*)malloc(sizeof(ListNode));
	ListNode* small =s_traval= (ListNode*)malloc(sizeof(ListNode));
	ListNode* cur = pHead;//用来遍历链表
	while (cur)
	{
		if (cur->val < x)
		{
			s_traval->next = cur;
			s_traval = s_traval->next;
		}
		else
		{
			l_traval->next=cur;
			l_traval = l_traval->next;
		}
		cur = cur->next;
	}
//合并链表
	l_traval->next = NULL;
	s_traval->next = large->next;

	ListNode* pos = small;
	small = small->next;
	free(pos);
	free(large);
	return small;
	
}
void Print(ListNode* phead)
{
    ListNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL");//模拟链表最后指向的是NULL
}

int main()
{
	ListNode* n1 = (ListNode*)malloc(sizeof(ListNode));//创建5个节点，为了测试分割链表函数
	ListNode* n2 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n3 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n4 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n5 = (ListNode*)malloc(sizeof(ListNode));

	ListNode* plist = n1;//指向头节点的头指针plist
	n1->val = 12;//给每个节点都赋值
	n2->val = 6;
	n3->val = 23;
	n4->val = 18;
	n5->val = 2;

	n1->next = n2;//手动构建链表
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	Print(plist);//打印分割之前的链表

	ListNode* newhead = partition(plist, 8);//分割后返回新的头节点

	printf("\n分割后:");
	Print(newhead);//打印分割之后的链表
	return 0;

}